![](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="96" height="96"><rect fill-opacity="0"/></svg>){kind=small}
IN previous article the implementation of the Ed25519 curve itself, the operations of addition and multiplication by a number, and the restoration of the second coordinate were considered. This article discusses how to effectively use these operations to electronically sign messages and work in I2P.
Unlike RSA, where the private and public key can be used directly, here you have to use a more complex scheme and introduce some additional object. EdDSA conceptually implements the algorithm DSA, extending it to the case of curves. The signature is a pair of numbers (R, S), for EdDSA each is 32 bytes long, the total length of the signature is 64 bytes. It is not the data itself that is signed, but the hash of it. SHA512 is used as the hash function. Further, small letters will denote numbers, and large letters will denote the corresponding point on the curve, obtained by multiplying the number by the base point B.
Let h be the hash of the message being signed, a the secret key, and A the corresponding public key (A = a*B). Let's take a random number r, and calculate R = r*B and s = r+h*a. The pair (R,s) will be the signature, where R is represented by its y coordinate.
When checking a signature, the recipient knows A and h and needs to check the truth of (R,s). To do this, check the equality: s*B = R+h*A.
Indeed (r+h*a)*B = r*B+h*a*B = R+h*A.
Note that s is calculated directly based on the secret key, and not the point generated by it, therefore errors in the implementation can lead to its immediate compromise. In particular, the poor choice of r. To avoid this, Bernstein suggests calculating r as a hash of half the secret key hash combined with the data being signed, but choosing r in some other way will not break the algorithm, that is, the signature values themselves will be different, but the result of the check will be the same. We will calculate r, as Bernstein suggests and as is done in the official I2P.
For further calculations, you will need a previously unused curve parameter l=
, such that l*B=0.
From this equality it immediately follows that the value of the factor before the point should not exceed l, otherwise it will only lead to an increase in the amount of calculations. If the multiplier exceeds l, then it must be taken modulo, in particular the value of h, which is a 64-byte SHA512 hash.
From this, in turn, it follows that the multiplier in the multiplication operation does not exceed 32 bytes and the most significant bit is always zero.
As you can see from the formulas, a signature requires one multiplication by the base point, and two multiplications are required to verify the signature: one by the base point, and the second by the public key.
For a base point, it makes sense to calculate the result of multiplication by different factors in advance. The simplest is a row (B, 2*B, 4*B, 8*B, ...) with a total of 255 points, which allows you to eliminate the doubling operation at each step. You can go further and expand the multiplier not in powers of two, but in powers of 16, and for every 4 bits of the multiplier add a calculated point from the array to the result. To do this, you will need to calculate and store 32*2*16 points, but this is done once for the duration of the entire work. Thus, multiplication by B is reduced to exactly 64 additions and message signing is carried out quickly. This is what it looks like in code.
Here Bi16 is an array of 64x16 points, and e this is a 32-byte multiplier in Little Endian. Instead of powers of 16, you can use expansions in powers of 256, this will lead to some acceleration, at the same time you will need to store 32 * 256 points.
To verify the signature, we will also need to multiply the public key, although it is the result of multiplying B, the multiplier is unknown to us, since this is the secret key. If you use this method, you will have to keep such an array for each of them, and in I2P there are a lot of public keys - each node from netdb has its own, of which there are about several thousand, which would lead to unjustified memory consumption. Therefore, in order to achieve operating speed comparable to other elliptic curves, we will have to improve the addition operation.
As noted in previous article, the slowest operation is division for each addition, which can be eliminated by moving to homogeneous coordinates. The implementation becomes less clear, but all implementations of elliptic cryptography are built there. Instead of two coordinates of a point (x, y), a third coordinate is entered that stores a common denominator, and instead of x and y their numerators are stored, that is, from homogeneous coordinates (X,Y,Z) the true coordinates are obtained as (X/Z, Y/Z ). In addition, the fourth coordinate T = X*Y/Z is introduced. The coordinates of the addition result are calculated using the following formulas:
X = (X1*Y2+Y1*X2)*(Z1*Z2-d*T1*T2)
Y = (Y1*Y2+X1*X2)*(Z1*Z2+d*T1*T2)
Z = (Z1*Z2-d*T1*T2)*(Z1*Z2+d*T1*T2)
T = (Y1*Y2+X1*X2)*(X1*Y2+Y1*X2)
As you can see, the labor-intensive operation of exponentiation in the process of addition and multiplication is no longer used.
Another disadvantage of homogeneous coordinates is the complexity of comparing two points: X and Y coordinates cannot be compared directly - they must be brought to a common denominator in one way or another, which requires additional calculations. To verify a signature, you need to compare points.
Let's rewrite the expression for checking the signature s*B=R+h*A as R=s*Bh*A.
Then, instead of reconstructing the X coordinate of a point from the Y coordinate from the signature, you can take the Y coordinate from (s*Bh*A), thereby saving another exponentiation and comparing numbers instead of points. This method requires a subtraction operation, which is implemented through additions and a unary minus, defined as (-X, Y, Z, -T). Thus, the subtraction operation is performed at the same speed as addition, and can be used for expansion in powers with negative coefficients, which allows reducing the memory footprint by 2 times.
The length of the I2P address with EdDSA is 391 bytes, the signature type code is 7, denoted in the documentation as EdDSA_SHA512_Ed25519.
The length of the secret and public keys is 32 bytes, the length of the signature is 64 bytes, the first 32 bytes are R in the form of the y coordinate, the second 32 bytes are s.
All numbers are sent to Little Endian.
EdDSA is currently the recommended signature type for RouterInfo.
Thus, two articles describe a complete and transparent implementation of EdDSA on top of the openssl library for working with large numbers, working at high speed and practically used in i2pd.
EdDSA signature algorithm
Unlike RSA, where the private and public key can be used directly, here you have to use a more complex scheme and introduce some additional object. EdDSA conceptually implements the algorithm DSA, extending it to the case of curves. The signature is a pair of numbers (R, S), for EdDSA each is 32 bytes long, the total length of the signature is 64 bytes. It is not the data itself that is signed, but the hash of it. SHA512 is used as the hash function. Further, small letters will denote numbers, and large letters will denote the corresponding point on the curve, obtained by multiplying the number by the base point B.
Let h be the hash of the message being signed, a the secret key, and A the corresponding public key (A = a*B). Let's take a random number r, and calculate R = r*B and s = r+h*a. The pair (R,s) will be the signature, where R is represented by its y coordinate.
When checking a signature, the recipient knows A and h and needs to check the truth of (R,s). To do this, check the equality: s*B = R+h*A.
Indeed (r+h*a)*B = r*B+h*a*B = R+h*A.
Note that s is calculated directly based on the secret key, and not the point generated by it, therefore errors in the implementation can lead to its immediate compromise. In particular, the poor choice of r. To avoid this, Bernstein suggests calculating r as a hash of half the secret key hash combined with the data being signed, but choosing r in some other way will not break the algorithm, that is, the signature values themselves will be different, but the result of the check will be the same. We will calculate r, as Bernstein suggests and as is done in the official I2P.
Efficient implementation of multiplication
For further calculations, you will need a previously unused curve parameter l=
, such that l*B=0. From this equality it immediately follows that the value of the factor before the point should not exceed l, otherwise it will only lead to an increase in the amount of calculations. If the multiplier exceeds l, then it must be taken modulo, in particular the value of h, which is a 64-byte SHA512 hash.
From this, in turn, it follows that the multiplier in the multiplication operation does not exceed 32 bytes and the most significant bit is always zero.
As you can see from the formulas, a signature requires one multiplication by the base point, and two multiplications are required to verify the signature: one by the base point, and the second by the public key.
For a base point, it makes sense to calculate the result of multiplication by different factors in advance. The simplest is a row (B, 2*B, 4*B, 8*B, ...) with a total of 255 points, which allows you to eliminate the doubling operation at each step. You can go further and expand the multiplier not in powers of two, but in powers of 16, and for every 4 bits of the multiplier add a calculated point from the array to the result. To do this, you will need to calculate and store 32*2*16 points, but this is done once for the duration of the entire work. Thus, multiplication by B is reduced to exactly 64 additions and message signing is carried out quickly. This is what it looks like in code.
EDDSAPoint res {zero, one};
for (int i = 0; i < 32; i++)
{
uint8_t x = e[i] & 0x0F; // 4 low bits
if (x > 0)
res = Sum (res, Bi16[i*2][x-1], ctx);
x = e[i] >> 4; // 4 high bits
if (x > 0)
res = Sum (res, Bi16[i*2+1][x-1], ctx);
}
Here Bi16 is an array of 64x16 points, and e this is a 32-byte multiplier in Little Endian. Instead of powers of 16, you can use expansions in powers of 256, this will lead to some acceleration, at the same time you will need to store 32 * 256 points.
To verify the signature, we will also need to multiply the public key, although it is the result of multiplying B, the multiplier is unknown to us, since this is the secret key. If you use this method, you will have to keep such an array for each of them, and in I2P there are a lot of public keys - each node from netdb has its own, of which there are about several thousand, which would lead to unjustified memory consumption. Therefore, in order to achieve operating speed comparable to other elliptic curves, we will have to improve the addition operation.
Addition in homogeneous coordinates
As noted in previous article, the slowest operation is division for each addition, which can be eliminated by moving to homogeneous coordinates. The implementation becomes less clear, but all implementations of elliptic cryptography are built there. Instead of two coordinates of a point (x, y), a third coordinate is entered that stores a common denominator, and instead of x and y their numerators are stored, that is, from homogeneous coordinates (X,Y,Z) the true coordinates are obtained as (X/Z, Y/Z ). In addition, the fourth coordinate T = X*Y/Z is introduced. The coordinates of the addition result are calculated using the following formulas:
X = (X1*Y2+Y1*X2)*(Z1*Z2-d*T1*T2)
Y = (Y1*Y2+X1*X2)*(Z1*Z2+d*T1*T2)
Z = (Z1*Z2-d*T1*T2)*(Z1*Z2+d*T1*T2)
T = (Y1*Y2+X1*X2)*(X1*Y2+Y1*X2)
As you can see, the labor-intensive operation of exponentiation in the process of addition and multiplication is no longer used.
Another disadvantage of homogeneous coordinates is the complexity of comparing two points: X and Y coordinates cannot be compared directly - they must be brought to a common denominator in one way or another, which requires additional calculations. To verify a signature, you need to compare points.
Subtracting two points on a curve
Let's rewrite the expression for checking the signature s*B=R+h*A as R=s*Bh*A.
Then, instead of reconstructing the X coordinate of a point from the Y coordinate from the signature, you can take the Y coordinate from (s*Bh*A), thereby saving another exponentiation and comparing numbers instead of points. This method requires a subtraction operation, which is implemented through additions and a unary minus, defined as (-X, Y, Z, -T). Thus, the subtraction operation is performed at the same speed as addition, and can be used for expansion in powers with negative coefficients, which allows reducing the memory footprint by 2 times.
I2P addresses with EdDSA
The length of the I2P address with EdDSA is 391 bytes, the signature type code is 7, denoted in the documentation as EdDSA_SHA512_Ed25519.
The length of the secret and public keys is 32 bytes, the length of the signature is 64 bytes, the first 32 bytes are R in the form of the y coordinate, the second 32 bytes are s.
All numbers are sent to Little Endian.
EdDSA is currently the recommended signature type for RouterInfo.
Thus, two articles describe a complete and transparent implementation of EdDSA on top of the openssl library for working with large numbers, working at high speed and practically used in i2pd.
